/** 206 迭代法
Definition for singly-linked list.
struct ListNode {
int val;
struct ListNode *next;
};
*/
struct ListNode* reverseList(struct ListNode* head){   // 这里的head里面的内容不能改写，如果要改写请传递二级指针
    struct ListNode * prev = NULL;
    struct ListNode * curr = head;
    while (curr) {
        struct ListNode * next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}
// 206 递归写法
struct ListNode* reverseList(struct ListNode* head){
    struct ListNode * new = NULL;

    if (!head || !head->next) return head;
    new = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return new;
}

/**
02.04 题 
Definition for singly-linked list.
struct ListNode {
int val;
struct ListNode *next;
};
*/
// 暴力求解
struct ListNode* partition(struct ListNode* head, int x){
    if (!head || !head->next) return head;
    struct ListNode *t1, *h1, *t2, *h2;
    h1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    h2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    t1 = h1;
    t2 = h2;
    t1->next = NULL;
    t2->next = NULL;
    while (head) {
        if (head->val < x) {
            t1->next = head;
            t1 = t1->next;
        } else {
            t2->next = head;
        t2 = t2->next;
        }
    head = head->next;
    }
    t1->next = h2->next;
    t2->next = NULL;
return h1->next;
}

/**
* 02.04 题 
Definition for singly-linked list.
struct ListNode {
int val;
struct ListNode *next;
};
*/
//双指针法
struct ListNode* partition(struct ListNode* head, int x){
    if (!head || !head->next) return head;
    struct ListNode *prev, *curr;
    prev = head;
    curr = head;
    while(curr) {
        if (curr->val < x) {
            int tmp = prev->val;
            prev->val = curr->val;
            curr->val = tmp;
            prev = prev->next;
        }
        curr = curr->next;
    }
    return head;
}

